後置轉前綴表示法

目標

您的目標是將一個後置表達式（逆波蘭表示法）轉換為其對應的前綴表達式（波蘭表示法），透過建立並遍歷運算式樹來完成。

演算法

1. 建立運算式樹： 從左到右處理後置表達式，並使用堆疊。
   • 當遇到一個操作數（例如：A、B）時，為其建立一個單節點樹，並將其壓入堆疊。
   • 當遇到一個運算子（例如：+、*）時，從堆疊中彈出兩棵樹。第一個彈出的是右子樹（T₂），第二個是左子樹（T₁）。以該運算子為根節點建立一棵新樹，並重新壓回堆疊。
2. 產生前綴字串： 在處理完所有符號後，堆疊中將包含完整的運算式樹。執行前序走訪（根節點 → 左子樹 → 右子樹）來產生最終的前綴表達式。

範例

針對後置表達式A B + C *，該演算法建立以下樹形結構：

  *
   / \
  +   C
 / \
A   B

前序走訪結果為前綴表達式：* + A B C。

輸入/輸出格式

輸入

• 第 1 行：一個整數N（1 ≤ N≤ 1000），代表符號數量。
• 第 2 行：後置表達式，包含N個符號，以空格分隔。

符號規則

• 操作數：單個大寫字母（A至Z）。
• 運算子：四種二元運算子：+、至、*、/。

輸出

• 一行包含對應的前綴表達式，符號之間以空格分隔。

範例

範例 1：

5

A B + C *

* + A B C

範例 2：

7

A B C * + D /

/ + A * B C D

範例 3：

7

A B + C D - *

* + A B - C D

限制條件